package ListDemo;

import java.util.Stack;

/*
* 1.链表以节点的方式来存储
* 2.每个节点包含data域,next域:指向下一个节点
* 3.链表的各个节点不一定是连续存放
* 4.链表分带头结点的链表和不带头结点的链表
* */
class Test{
    public static void main(String[] args) {
        singleList s1 = new singleList();
        singleList s2 = new singleList();

        s1.addOrder(1,"孙悟空","齐天大圣");
        s1.addOrder(3,"张三丰","一眉道人");
        s1.addOrder(5,"张yi丰","一眉道人");

        s2.addOrder(2,"赵云","常山赵子龙");
        s2.addOrder(4,"张er丰","一眉道人");
        s2.addOrder(6,"张yi丰","一眉道人");

        heroNode2 merge = singleList.merge(s1.getHead(), s2.getHead());
        singleList.show(merge);
    }
}


public class ListDemo {
    public static void main(String[] args) {
        singleList sl = new singleList();
        try {
            sl.addOrder(2,"孙悟空","齐天大圣");
            sl.addOrder(1,"赵云","常山赵子龙");
            sl.addOrder(3,"张三丰","一眉道人");
            sl.addOrder(4,"张er丰","一眉道人");
            sl.addOrder(5,"张yi丰","一眉道人");

            //System.out.println("链表中节点个数="+sl.getSize(sl.getHead()));

            /*heroNode k = sl.getK(sl.getHead(), 2);
            System.out.println(k.toString());*/
            //sl.reverseHead(sl.getHead());


        } catch (Exception e) {
            throw new RuntimeException("节点已经存在,无法添加");
        }finally {
            singleList.show(sl.getHead());
            singleList.printReverse(sl.getHead());
        }
    }
}

class singleList{
    heroNode2 head = new heroNode2(0,"666","666");// 哨兵位

    public heroNode2 getHead() {
        return head;
    }

    // 删除节点
    public void delete(int no){
        heroNode2 temp = head;
        while(true){
            if(temp.next == null){
                System.out.println("节点不存在,无法删除");
                break;
            }

            if(temp.next.no == no){
                temp.next = temp.next.next;
                break;
            }
            temp = temp.next;
        }
    }

    // 更新节点
    public void update(heroNode2 newHeroNode){
            // 链表为空,直接插入
            if(head.next == null){
                head.next = newHeroNode;
                return;
            }
            // 链表非空,遍历
            heroNode2 temp = head.next;
            while(true){
                if(temp.no == newHeroNode.no){
                    temp.name = newHeroNode.name;
                    temp.nickname = newHeroNode.nickname;
                    break;
                }

                if(temp.next == null){
                    temp.next = newHeroNode;
                    break;
                }
                temp = temp.next;
            }

    }


    // 添加节点按照no有序插入
    public void addOrder(int no,String name,String nickname){
        heroNode2 newNode = new heroNode2(no,name,nickname);
        heroNode2 tmp = head;
        boolean flag = false;// flag 标志添加的节点是否存在
        // 链表非空,循环遍历
        while(true){
            if(tmp.next == null){// 下一个节点为空,赋值为newNode
                tmp.next = newNode;
                break;
            }

            if(tmp.next.no > newNode.no){
                newNode.next = tmp.next;
                tmp.next = newNode;
                break;
            }else if(tmp.next.no == newNode.no){// no相等表示英雄重复,抛出异常
                flag = true;
                break;
            }
            tmp = tmp.next;
        }
        if(flag){
            throw new RuntimeException();
        }
    }

    // 添加节点到单向链表
    public void addNode(int no,String name,String nickname){
        heroNode2 newNode = new heroNode2(no,name,nickname);

        // head 节点不能动,添加一个辅助节点,遍历链表到最后进行添加
        heroNode2 tmp = head;
        while(tmp.next != null){
            tmp = tmp.next;
        }
        tmp.next = newNode;
        newNode.next = null;
    }

    // 显示链表,遍历
    public static void show(heroNode2 head){
        heroNode2 tmp = head.next;
        while(tmp != null){
            System.out.println(tmp);
            tmp = tmp.next;
        }
    }

    // 求单链表中节点的个数
    public int getSize(heroNode2 head){
        // 链表为空,返回零
        if(head.next == null){
            return 0;
        }
        heroNode2 cur = head.next;
        // 链表非空,遍历
        int length = 0;
        while(cur!=null){
            length++;
            cur = cur.next;
        }
        return length;
    }

    // 倒数第k个节点
    public heroNode2 getK(heroNode2 head, int k){
        heroNode2 cur = head;
        // 如果链表为空,直接返回null
        if(head.next == null){
            return null;
        }
        //链表非空
        // 获取链表元素个数
        int size = getSize(head);

        // 判断索引是否合法
        if(k<0 || k>size){
            return null;
        }
        // 遍历找到size-k位置的元素
        int length = size-k;
        while(length>=0){
            cur = cur.next;
            length--;
        }
        return cur;
    }

    // 翻转链表(百度面试题)
    /*
    * 思路:
    * 定义一个reverseHead节点
    * 依次遍历需要翻转的链表,得到,每一个元素,将其头插到新的链表上
    * head.next = reverseHead.next
    * */
    public void reverseHead(heroNode2 head){
        // 创建伪头节点,用于接收遍历得到的节点
        heroNode2 reserveNode = new heroNode2(1,"999","999");

        while(true){

            // 当链表为空时,直接返回
            if(head.next == null){
                head.next = reserveNode.next;
                break;
            }

            // reserveNode的下一个节点为空,直接插入
            if(reserveNode.next == null){
                reserveNode.next = head.next;
                head.next = head.next.next;// 遍历
                reserveNode.next.next = null;
            }else {
                // 临时变量next用来记录reverseNode的下一个节点
                heroNode2 next = reserveNode.next;
                reserveNode.next = head.next;
                head.next = head.next.next;
                reserveNode.next.next = next;
            }
        }
    }

    // 倒叙打印(百度面试题) stack栈
    public static void printReverse(heroNode2 head){
        Stack<heroNode2> stack = new Stack<>();
        while(head.next != null){
            stack.add(head.next);
            head = head.next;
        }
        while(stack.size()>0){
            System.out.println(stack.pop().toString());
        }
    }

    // 合并两个有序的单链表
    public static heroNode2 merge(heroNode2 head1, heroNode2 head2){
        heroNode2 newNode = new heroNode2(1,"2","3");
        heroNode2 cur = newNode;
        if(head1.next == null){
            return head2;
        }
        if(head2.next == null){
            return head1;
        }
        while(true){
            if(head1.next == null){
                cur.next = head2.next;
                break;
            }
            if(head2.next == null){
                cur.next = head1.next;
                break;
            }

            if(head1.next.no >= head2.next.no){
                cur.next = head2.next;
                head2.next = head2.next.next;
            }else{
                cur.next = head1.next;
                head1.next = head1.next.next;
            }
            cur = cur.next;
            cur.next = null;
        }
        return newNode;
    }
}

// 英雄节点
class heroNode2 {
    public int no;
    public String name;
    public String nickname;//昵称
    public heroNode2 next;

    public heroNode2(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    // 重写toString方法
    @Override
    public String toString() {
        return "heroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname+
                '}';
    }
}


